home *** CD-ROM | disk | FTP | other *** search
/ OpenGL Superbible (2nd Edition) / OpenGL SuperBible e2.iso / tools / Mesa-3.0 / SRC-GLU / TESSELAT.C < prev   
Encoding:
C/C++ Source or Header  |  1997-07-24  |  9.8 KB  |  454 lines
  1. /* $Id: tesselat.c,v 1.5 1997/07/24 01:28:44 brianp Exp $ */
  2.  
  3. /*
  4.  * Mesa 3-D graphics library
  5.  * Version:  2.4
  6.  * Copyright (C) 1995-1997  Brian Paul
  7.  *
  8.  * This library is free software; you can redistribute it and/or
  9.  * modify it under the terms of the GNU Library General Public
  10.  * License as published by the Free Software Foundation; either
  11.  * version 2 of the License, or (at your option) any later version.
  12.  *
  13.  * This library is distributed in the hope that it will be useful,
  14.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16.  * Library General Public License for more details.
  17.  *
  18.  * You should have received a copy of the GNU Library General Public
  19.  * License along with this library; if not, write to the Free
  20.  * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  21.  */
  22.  
  23.  
  24. /*
  25.  * $Log: tesselat.c,v $
  26.  * Revision 1.5  1997/07/24 01:28:44  brianp
  27.  * changed precompiled header symbol from PCH to PC_HEADER
  28.  *
  29.  * Revision 1.4  1997/05/28 02:29:38  brianp
  30.  * added support for precompiled headers (PCH), inserted APIENTRY keyword
  31.  *
  32.  * Revision 1.3  1997/02/17 17:24:58  brianp
  33.  * more tesselation changes (Randy Frank)
  34.  *
  35.  * Revision 1.2  1997/02/13 18:31:57  brianp
  36.  * fixed some numerical precision problems (Randy Frank)
  37.  *
  38.  * Revision 1.1  1996/09/27 01:19:39  brianp
  39.  * Initial revision
  40.  *
  41.  */
  42.  
  43.  
  44. /*
  45.  * This file is part of the polygon tesselation code contributed by
  46.  * Bogdan Sikorski
  47.  */
  48.  
  49.  
  50. #ifdef PC_HEADER
  51. #include "all.h"
  52. #else
  53. #include <stdlib.h>
  54. #include <math.h>
  55. #include "tess.h"
  56. #endif
  57.  
  58.  
  59.  
  60. static GLboolean edge_flag;
  61.  
  62. static void emit_triangle(GLUtriangulatorObj *, tess_vertex *,
  63.     tess_vertex *,tess_vertex *);
  64.  
  65. static void emit_triangle_with_edge_flag(GLUtriangulatorObj *,
  66.      tess_vertex *,GLboolean,tess_vertex *,GLboolean,
  67.      tess_vertex *,GLboolean);
  68.  
  69. static GLdouble twice_the_triangle_area(
  70.     tess_vertex *va,
  71.     tess_vertex *vb,
  72.     tess_vertex *vc)
  73. {
  74.     return     (vb->x - va->x)*(vc->y - va->y) - (vb->y - va->y)*(vc->x - va->x);
  75. }
  76.  
  77. static GLboolean left(
  78.     GLdouble A,
  79.     GLdouble B,
  80.     GLdouble C,
  81.     GLdouble x,
  82.     GLdouble y)
  83. {
  84.     if(A*x+B*y+C > -EPSILON)
  85.         return GL_TRUE;
  86.     else
  87.         return GL_FALSE;
  88. }
  89.  
  90. static GLboolean right(
  91.     GLdouble A,
  92.     GLdouble B,
  93.     GLdouble C,
  94.     GLdouble x,
  95.     GLdouble y)
  96. {
  97.     if(A*x+B*y+C < EPSILON)
  98.         return GL_TRUE;
  99.     else
  100.         return GL_FALSE;
  101. }
  102.  
  103. static GLint convex_ccw(
  104.     tess_vertex *va,
  105.     tess_vertex *vb,
  106.     tess_vertex *vc,
  107.     GLUtriangulatorObj *tobj)
  108. {
  109.     GLdouble    d;
  110.  
  111.     d = twice_the_triangle_area(va,vb,vc);
  112.  
  113.     if (d > EPSILON ) {
  114.         return 1;
  115.     } else if (d < -EPSILON ) {
  116.         return 0;
  117.     } else {
  118.         return -1;
  119.     }
  120. }
  121.  
  122. static GLint convex_cw(
  123.     tess_vertex *va,
  124.     tess_vertex *vb,
  125.     tess_vertex *vc,
  126.     GLUtriangulatorObj *tobj)
  127. {
  128.     GLdouble    d;
  129.  
  130.     d = twice_the_triangle_area(va,vb,vc);
  131.  
  132.     if (d < -EPSILON ) {
  133.         return 1;
  134.     } else if (d > EPSILON ) {
  135.         return 0;
  136.     } else {
  137.         return -1;
  138.     }
  139. }
  140.  
  141. static GLboolean diagonal_ccw(
  142.     tess_vertex *va,
  143.     tess_vertex *vb,
  144.     GLUtriangulatorObj *tobj,
  145.     tess_contour *contour)
  146. {
  147.     tess_vertex *vc=va->next , *vertex , *shadow_vertex;
  148.     struct
  149.     {
  150.         GLdouble A,B,C;
  151.     } ac,cb,ba;
  152.     GLdouble x,y;
  153.  
  154.     GLint     res = convex_ccw(va,vc,vb,tobj);
  155.     if (res == 0) return GL_FALSE;
  156.     if (res == -1) return GL_TRUE;
  157.  
  158.     ba.A=vb->y - va->y;
  159.     ba.B=va->x - vb->x;
  160.     ba.C= -ba.A*va->x - ba.B*va->y;
  161.     ac.A=va->y - vc->y;
  162.     ac.B=vc->x - va->x;
  163.     ac.C= -ac.A*vc->x - ac.B*vc->y;
  164.     cb.A=vc->y - vb->y;
  165.     cb.B=vb->x - vc->x;
  166.     cb.C= -cb.A*vb->x - cb.B*vb->y;
  167.     for(vertex=vb->next;vertex!=va;vertex=vertex->next)
  168.     {
  169.         shadow_vertex=vertex->shadow_vertex;
  170.         if(shadow_vertex!=NULL && 
  171.             (shadow_vertex==va || shadow_vertex==vb || shadow_vertex==vc))
  172.             continue;
  173.         x=vertex->x;
  174.         y=vertex->y;
  175.         if(left(ba.A,ba.B,ba.C,x,y) &&
  176.             left(ac.A,ac.B,ac.C,x,y) &&
  177.             left(cb.A,cb.B,cb.C,x,y))
  178.             return GL_FALSE;
  179.     }
  180.     return GL_TRUE;
  181. }
  182.  
  183. static GLboolean diagonal_cw(
  184.     tess_vertex *va,
  185.     tess_vertex *vb,
  186.     GLUtriangulatorObj *tobj,
  187.     tess_contour *contour)
  188. {
  189.     tess_vertex *vc=va->next , *vertex , *shadow_vertex;
  190.     struct
  191.     {
  192.         GLdouble A,B,C;
  193.     } ac,cb,ba;
  194.     GLdouble x,y;
  195.  
  196.     GLint     res = convex_cw(va,vc,vb,tobj);
  197.     if (res == 0) return GL_FALSE;
  198.     if (res == -1) return GL_TRUE;
  199.  
  200.     ba.A=vb->y - va->y;
  201.     ba.B=va->x - vb->x;
  202.     ba.C= -ba.A*va->x - ba.B*va->y;
  203.     ac.A=va->y - vc->y;
  204.     ac.B=vc->x - va->x;
  205.     ac.C= -ac.A*vc->x - ac.B*vc->y;
  206.     cb.A=vc->y - vb->y;
  207.     cb.B=vb->x - vc->x;
  208.     cb.C= -cb.A*vb->x - cb.B*vb->y;
  209.     for(vertex=vb->next;vertex!=va;vertex=vertex->next)
  210.     {
  211.         shadow_vertex=vertex->shadow_vertex;
  212.         if(shadow_vertex!=NULL && 
  213.             (shadow_vertex==va || shadow_vertex==vb || shadow_vertex==vc))
  214.             continue;
  215.         x=vertex->x;
  216.         y=vertex->y;
  217.         if(right(ba.A,ba.B,ba.C,x,y) &&
  218.             right(ac.A,ac.B,ac.C,x,y) &&
  219.             right(cb.A,cb.B,cb.C,x,y))
  220.             return GL_FALSE;
  221.     }
  222.     return GL_TRUE;
  223. }
  224.  
  225. static void clip_ear(
  226.     GLUtriangulatorObj *tobj,
  227.     tess_vertex *v,
  228.     tess_contour *contour)
  229. {
  230.     emit_triangle(tobj,v->previous,v,v->next);
  231.     /* the first in the list */
  232.     if(contour->vertices==v)
  233.     {
  234.         contour->vertices=v->next;
  235.         contour->last_vertex->next=v->next;
  236.         v->next->previous=contour->last_vertex;
  237.     }
  238.     else
  239.     /* the last ? */
  240.     if(contour->last_vertex==v)
  241.     {
  242.         contour->vertices->previous=v->previous;
  243.         v->previous->next=v->next;
  244.         contour->last_vertex=v->previous;
  245.     }
  246.     else
  247.     {
  248.         v->next->previous=v->previous;
  249.         v->previous->next=v->next;
  250.     }
  251.     free(v);
  252.     --(contour->vertex_cnt);
  253. }
  254.  
  255. static void clip_ear_with_edge_flag(
  256.     GLUtriangulatorObj *tobj,
  257.     tess_vertex *v,
  258.     tess_contour *contour)
  259. {
  260.     emit_triangle_with_edge_flag(tobj,v->previous,v->previous->edge_flag,
  261.         v,v->edge_flag,v->next,GL_FALSE);
  262.     v->previous->edge_flag=GL_FALSE;
  263.     /* the first in the list */
  264.     if(contour->vertices==v)
  265.     {
  266.         contour->vertices=v->next;
  267.         contour->last_vertex->next=v->next;
  268.         v->next->previous=contour->last_vertex;
  269.     }
  270.     else
  271.     /* the last ? */
  272.     if(contour->last_vertex==v)
  273.     {
  274.         contour->vertices->previous=v->previous;
  275.         v->previous->next=v->next;
  276.         contour->last_vertex=v->previous;
  277.     }
  278.     else
  279.     {
  280.         v->next->previous=v->previous;
  281.         v->previous->next=v->next;
  282.     }
  283.     free(v);
  284.     --(contour->vertex_cnt);
  285. }
  286.  
  287. static void triangulate_ccw(
  288.     GLUtriangulatorObj *tobj,
  289.     tess_contour *contour)
  290. {
  291.     tess_vertex *vertex;
  292.     GLuint vertex_cnt=contour->vertex_cnt;
  293.  
  294.     while(vertex_cnt > 3)
  295.     {
  296.         vertex=contour->vertices;
  297.         while(diagonal_ccw(vertex,vertex->next->next,tobj,contour)==GL_FALSE &&
  298.             tobj->error==GLU_NO_ERROR)
  299.             vertex=vertex->next;
  300.         if(tobj->error!=GLU_NO_ERROR)
  301.             return;
  302.         clip_ear(tobj,vertex->next,contour);
  303.         --vertex_cnt;
  304.     }
  305. }
  306.  
  307. static void triangulate_cw(
  308.     GLUtriangulatorObj *tobj,
  309.     tess_contour *contour)
  310. {
  311.     tess_vertex *vertex;
  312.     GLuint vertex_cnt=contour->vertex_cnt;
  313.  
  314.     while(vertex_cnt > 3)
  315.     {
  316.         vertex=contour->vertices;
  317.         while(diagonal_cw(vertex,vertex->next->next,tobj,contour)==GL_FALSE &&
  318.             tobj->error==GLU_NO_ERROR)
  319.             vertex=vertex->next;
  320.         if(tobj->error!=GLU_NO_ERROR)
  321.             return;
  322.         clip_ear(tobj,vertex->next,contour);
  323.         --vertex_cnt;
  324.     }
  325. }
  326.  
  327. static void triangulate_ccw_with_edge_flag(
  328.     GLUtriangulatorObj *tobj,
  329.     tess_contour *contour)
  330. {
  331.     tess_vertex *vertex;
  332.     GLuint vertex_cnt=contour->vertex_cnt;
  333.  
  334.     while(vertex_cnt > 3)
  335.     {
  336.         vertex=contour->vertices;
  337.         while(diagonal_ccw(vertex,vertex->next->next,tobj,contour)==GL_FALSE &&
  338.             tobj->error==GLU_NO_ERROR)
  339.             vertex=vertex->next;
  340.         if(tobj->error!=GLU_NO_ERROR)
  341.             return;
  342.         clip_ear_with_edge_flag(tobj,vertex->next,contour);
  343.         --vertex_cnt;
  344.     }
  345. }
  346.  
  347. static void triangulate_cw_with_edge_flag(
  348.     GLUtriangulatorObj *tobj,
  349.     tess_contour *contour)
  350. {
  351.     tess_vertex *vertex;
  352.     GLuint vertex_cnt=contour->vertex_cnt;
  353.  
  354.     while(vertex_cnt > 3)
  355.     {
  356.         vertex=contour->vertices;
  357.         while(diagonal_cw(vertex,vertex->next->next,tobj,contour)==GL_FALSE &&
  358.             tobj->error==GLU_NO_ERROR)
  359.             vertex=vertex->next;
  360.         if(tobj->error!=GLU_NO_ERROR)
  361.             return;
  362.         clip_ear_with_edge_flag(tobj,vertex->next,contour);
  363.         --vertex_cnt;
  364.     }
  365. }
  366.  
  367. void tess_tesselate(GLUtriangulatorObj *tobj)
  368. {
  369.     tess_contour *contour;
  370.  
  371.     for(contour=tobj->contours;contour!=NULL;contour=contour->next)
  372.     {
  373.         if(contour->orientation==GLU_CCW) {
  374.             triangulate_ccw(tobj,contour);
  375.         } else {
  376.             triangulate_cw(tobj,contour);
  377.         }
  378.         if(tobj->error!=GLU_NO_ERROR)
  379.             return;
  380.  
  381.         /* emit the last triangle */
  382.         emit_triangle(tobj,contour->vertices,contour->vertices->next,
  383.             contour->vertices->next->next);
  384.     }
  385. }
  386.  
  387. void tess_tesselate_with_edge_flag(GLUtriangulatorObj *tobj)
  388. {
  389.     tess_contour *contour;
  390.  
  391.     edge_flag=GL_TRUE;
  392.     /* first callback with edgeFlag set to GL_TRUE */
  393.     (tobj->callbacks.edgeFlag)(GL_TRUE);
  394.  
  395.     for(contour=tobj->contours;contour!=NULL;contour=contour->next)
  396.     {
  397.         if(contour->orientation==GLU_CCW)
  398.             triangulate_ccw_with_edge_flag(tobj,contour);
  399.         else
  400.             triangulate_cw_with_edge_flag(tobj,contour);
  401.         if(tobj->error!=GLU_NO_ERROR)
  402.             return;
  403.         /* emit the last triangle */
  404.         emit_triangle_with_edge_flag(tobj,contour->vertices,
  405.             contour->vertices->edge_flag,contour->vertices->next,
  406.             contour->vertices->next->edge_flag,contour->vertices->next->next,
  407.             contour->vertices->next->next->edge_flag);
  408.     }
  409. }
  410.  
  411. static void emit_triangle(
  412.     GLUtriangulatorObj *tobj,
  413.     tess_vertex *v1,
  414.     tess_vertex *v2,
  415.     tess_vertex *v3)
  416. {
  417.     (tobj->callbacks.begin)(GL_TRIANGLES);
  418.     (tobj->callbacks.vertex)(v1->data);
  419.     (tobj->callbacks.vertex)(v2->data);
  420.     (tobj->callbacks.vertex)(v3->data);
  421.     (tobj->callbacks.end)();
  422. }
  423.  
  424. static void emit_triangle_with_edge_flag(
  425.     GLUtriangulatorObj *tobj,
  426.     tess_vertex *v1,
  427.     GLboolean edge_flag1,
  428.     tess_vertex *v2,
  429.     GLboolean edge_flag2,
  430.     tess_vertex *v3,
  431.     GLboolean edge_flag3)
  432. {
  433.     (tobj->callbacks.begin)(GL_TRIANGLES);
  434.     if(edge_flag1!=edge_flag)
  435.     {
  436.         edge_flag = (edge_flag==GL_TRUE ? GL_FALSE : GL_TRUE);
  437.         (tobj->callbacks.edgeFlag)(edge_flag);
  438.     }
  439.     (tobj->callbacks.vertex)(v1->data);
  440.     if(edge_flag2!=edge_flag)
  441.     {
  442.         edge_flag = (edge_flag==GL_TRUE ? GL_FALSE : GL_TRUE);
  443.         (tobj->callbacks.edgeFlag)(edge_flag);
  444.     }
  445.     (tobj->callbacks.vertex)(v2->data);
  446.     if(edge_flag3!=edge_flag)
  447.     {
  448.         edge_flag = (edge_flag==GL_TRUE ? GL_FALSE : GL_TRUE);
  449.         (tobj->callbacks.edgeFlag)(edge_flag);
  450.     }
  451.     (tobj->callbacks.vertex)(v3->data);
  452.     (tobj->callbacks.end)();
  453. }
  454.